300. 最长递增子序列

Similar Question

Solution Tips

方案一: 暴力法 (超时)

var lengthOfLIS = function(nums) {
    // 想不出来, 立马切换回溯+记忆化搜索, 尝试暴力解决
    let res = nums.length > 0 ? 1 : 0;

    for (let i = 0; i < nums.length; i++) {
        backtracking([nums[i]], i)
    }
    return res;

    function backtracking(chosen, cur) {
        if (cur.length === nums.length) return;
        // 根据 chosen 的最后一个值的不同, 还有 cur ,能找到的最长子序列都是有所不同的
        // 如果要做记忆化就只能两者为 key ,但是真的会有重复的么?

        // 选择当前元素为起点构建序列, 不是回溯, 还不如普通暴力
        // 递归也能实现普通暴力才对
        // 不好记忆, 想不到咋弄

        for (let i = cur; i < nums.length; i++) {
            const n = chosen.length;
            if (nums[i] > chosen[n - 1]) {
                // 选择当前数字构成子序列
                chosen.push(nums[i]);
                // 更新最长子序列
                res = Math.max(res, n + 1);
                backtracking(chosen, i + 1);
                // 回溯
                chosen.pop();
            }
        }
    }
};
console.log(lengthOfLIS([10,9,2,5,3,7,101,18]));

方案二: 动态规划

题解GIF: Loading Question... - 力扣（LeetCode）

const lengthOfLIS = (nums) => {i
    let dp = Array(nums.length).fill(1);
    let result = 1;

    for(let i = 1; i < nums.length; i++) {
        for(let j = 0; j < i; j++) {
            if(nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j]+1);
            }
        }
        result = Math.max(result, dp[i]);
    }

    return result;
};

方案三: 贪心 + 二分查找

Loading Question... - 力扣（LeetCode）